package com.jojo.intermediate.day12_linkedList;

import com.jojo.elementary.entity.ListNode;

/**
 * 24、两两交换链表中的节点
 *
 * 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
 * 你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
 *
 * 示例 1：
 * 输入：head = [1,2,3,4]
 * 输出：[2,1,4,3]
 *
 * 示例 2：
 * 输入：head = []
 * 输出：[]
 *
 * 示例 3：
 * 输入：head = [1]
 * 输出：[1]
 */
public class SwapListElement {

    /** myCode 迭代 */
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode first = new ListNode(0);
        first.next = head;
        ListNode pre = first;
        ListNode cur = head;
        ListNode next;
        while (cur != null && cur.next != null){
            next = cur.next;
            ListNode temp = next.next;
            pre.next = next;
            next.next = cur;
            cur.next = temp;
            pre = cur;
            cur = temp;
        }
        return first.next;
    }

    /** pe.递归 */
    public ListNode swapPairs2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs2(newHead.next);
        newHead.next = head;
        return newHead;
    }
}
